// Copyright 2024 Tvux
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//      http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

package _275

// hIndex
// 时间复杂度 O(n)
//func hIndex(citations []int) int {
//	end := len(citations)
//	h := 0
//	for i := end - 1; i >= 0; i-- {
//		if citations[i] >= end-i {
//			h++
//		} else {
//			break
//		}
//	}
//	return h
//}

// hIndex
// 因为这题已经保证数组是有序的了，所以也可以想到二分查找
// 时间复杂度 O(logn)
func hIndex(citations []int) int {
	n := len(citations)
	left, right := 1, n
	for left <= right {
		mid := left + (right-left)>>1
		if citations[n-mid] >= mid {
			// 判断一下当前是不是有mid个数大于等于mid，如果是，则在右边区间继续找
			left = mid + 1
		} else {
			right = mid - 1
		}
	}
	// left > right
	return right
}

// 题目的意思就是给你一个数组，求一个最大的h，使得数组中至少有h个数都大于等于h
//
// 为什么想到排序？为什么想到排序之后可以使用二分来找？
// 主要是因为如果h=2，那么就说明数组中必有0个数大于等于0，必有1个数大于等于1，必有2个数大于等于2
// 如果没有3个数大于等于3，那么也必没有4个数大于等于4
// 所以这是一个单调的，如果数组是有序的，则可以使用二分一次减少一半的搜索区间。
//
// 然后下标0可以不用加入区间，因为必有0个数大于等于0
// 0 1 3 5 6
// 0 1 2 3 4
// 因为必有0个数都大于等于0，所以0不用加入遍历区间
// left=1, right=len(citations)=5
// for left <= right
// mid = (left+right)/2 = 3
// nums[5-3]=nums[2]=3>=mid left = mid+1 left =4
